package tree;

import org.junit.Test;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

/**
 * 完全二叉树定义: null只能出现在最后一层, 不能出现在其他层. 且null靠右对齐.
 */
public class CheckCompletenessOfABinaryTree958 {

    @Test
    public void testDfs() {
        // true
        TreeNode t1 = TreeNode.buildTree(Arrays.asList(1,2,3,5));
        System.out.println(isCompleteTree(t1));

        // true
        TreeNode t2 = TreeNode.buildTree(Arrays.asList(1,2,3,4,5,6));
        System.out.println(isCompleteTree(t2));

        // false, 因为null出现在了倒数第二层.
        TreeNode t3 = TreeNode.buildTree(Arrays.asList(1,2,3,4,5,6,7,8,9,10,11,12,13,null,null,15));
        System.out.println(isCompleteTree(t3));
    }

    public boolean isCompleteTree(TreeNode root) {
        return BFS.isCompleteTree(root);
    }

    public static class BFS {
        public static boolean isCompleteTree(TreeNode root) {
            Queue<TreeNode> q = new LinkedList<>();
            q.add(root);
            while (!q.isEmpty()) {
                TreeNode node = q.remove();
                if (node != null) {
                    // 孩子节点都有可能是null
                    q.add(node.left);
                    q.add(node.right);
                } else {
                    // 发现队列中出现null了
                    break;
                }
            }
            // 队列中剩余节点都必须时null
            while (!q.isEmpty()) {
                TreeNode node = q.remove();
                if (node != null) {
                    return false;
                }
            }
            return true;
        }
    }

    // 可优化点: COMPLETE和FULL两种状态可以合并
    // 当前还有问题: null节点只能出现在最后一层, 现在没有判断.
    public static class DFS {
        public static boolean isCompleteTree(TreeNode root) {
            Summary s = computeSummaryRecursively(root);
            return s.status == Status.FULL || s.status == Status.COMPLETE;
        }

        public static Summary computeSummaryRecursively(TreeNode root) {
            if (root == null) {
                return new Summary(0, 0, Status.FULL);
            }
            Summary leftSummary = computeSummaryRecursively(root.left);
            Summary rightSummary = computeSummaryRecursively(root.right);

            if (leftSummary.status == Status.FULL && rightSummary.status == Status.FULL) {
                // leftSummary.maxDepth = leftSummary.minDepth
                // rightSummary.maxDepth = rightSummary.minDepth

                if (leftSummary.maxDepth == rightSummary.maxDepth) {
                    return new Summary(leftSummary.maxDepth + 1, rightSummary.minDepth + 1, Status.FULL);
                } else if (leftSummary.maxDepth > rightSummary.maxDepth) {
                    return new Summary(leftSummary.maxDepth + 1, rightSummary.minDepth + 1, Status.COMPLETE);
                }
            }

            if ((leftSummary.status == Status.FULL || leftSummary.status == Status.COMPLETE) &&
                    (rightSummary.status == Status.FULL || rightSummary.status == Status.COMPLETE)) {
                if (leftSummary.minDepth >= rightSummary.maxDepth) {
                    return new Summary(leftSummary.maxDepth + 1, rightSummary.minDepth + 1, Status.COMPLETE);
                }
            }

            return new Summary(-1, -1, Status.NOT_COMPLETE);
        }

        enum Status {
            FULL,
            COMPLETE,
            NOT_COMPLETE
        }

        static class Summary {
            int maxDepth;
            int minDepth;
            Status status;

            public Summary(int maxDepth, int minDepth, Status status) {
                this.maxDepth = maxDepth;
                this.minDepth = minDepth;
                this.status = status;
            }
        }
    }
}
